// https://www.luogu.com.cn/problem/P2871

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> weights(n + 1), values(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &weights[i], &values[i]);
    }

    vector<int> dp(m+1);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i]);
        }
    }

    printf("%d\n", dp[m]);

    return 0;
}